package cn.fxzhang.leetcode.no00;

/**
 * 4. 寻找两个正序数组的中位数
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 1 <= m + n <= 2000
 * 类型： 数组
 * 题解： 合并后取中位数
 * 时间复杂度：O(N), N是数组中的元素数量
 * 空间复杂度：O(N), N是数组中的元素数量
 *
 * 提交记录(1/1)：
 * 执行用时: 3 ms, 击败了82.42%
 * 内存消耗: 39.7 MB, 击败了58.56%
 *
 * 【困难】通过次数373,903提交次数938,347
 * todo O(log (m+n))的解法
 * @author 张晓帆
 * @date 2021/4/2
 */
public class P0004_Median_Of_Two_Sorted_Arrays {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] nums = merge(nums1, nums2);
        int len = nums.length;
        if (len == 0){
            return 0;
        }
        return len%2==1? nums[len/2]:(double)(nums[len/2]+nums[len/2-1])/2;
    }

    private int[] merge(int[] nums1, int[] nums2) {
        int[] num = new int[nums1.length + nums2.length];
        int i = 0;
        int j = 0;
        while (i<nums1.length || j<nums2.length){
            if (i == nums1.length || j<nums2.length && nums2[j]<nums1[i]){
                num[i+j] = nums2[j];
                j++;
            } else {
                num[i+j] = nums1[i];
                i++;
            }
        }
        return num;
    }

}
